Problem

Time limit : 2sec / Memory limit : 256MB

求一个$k$的倍数使其数位和最小，输出数位和，$k \leqslant 10^5$。

传送门

Solution

考虑极端情况数字是可能爆long long甚至__int128这种东西的

所以思考的方向是对于数位进行处理

考虑每一个数都能从$1$通过以下两种操作来得到：

乘$10$，数位和不变
加$1$，并且数位和$+1$

在$\text{mod}\ k$的意义下进行计算，把$0 \sim k-1$中的每一个数看成一个点，$i$向$i+1$连一条权值为$1$的边，$i$向$10i$连一条权值为$0$的边，从$1$到$0$跑最短路即可

这时有一个问题，上面说了，$+1$的时候必须保证数位和$+1$，所以连续走$10$次及以上权值为$1$的边是不合法的。但可以发现这样走一定不是最短路（可以在乘$10$之前走$1$步然后再乘$10$），所以不影响答案。

我们其实也可以得到一种等价的做法：

$k$个点表示$\text{mod}\ k=0\sim k-1$的最小数字和，起点是$1\sim k-1(d_i=i)$，终点为$0$，$x$向$(x*10+0 \sim 9) \text{mod}\ k$连边权为$0\sim 9$的边，跑最短路。

Code:

Click to show/hide the code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 1e5 + 10;
int n, m, first[MAXN], tot, d[MAXN], s, t;

struct edge { int from, v, w; } e[20 * MAXN];
struct Node
{
	int x, d;
	bool operator <(const Node &b)const
	{
		return d > b.d;
	}
}cyc;
priority_queue<Node> q;
inline void insert(int u, int v, int w)
{
	tot++; e[tot].v = v; e[tot].w = w; e[tot].from = first[u]; first[u] = tot;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (register int i = 1; i <= n; i++)
		for (register int j = 0; j <= 9; j++)insert(i, ((i - 1) * 10 + j) % n + 1, j);
	for (register int j = 1; j <= 9; j++) insert(0, j + 1, j);
	s = 0; t = 1;
	memset(d, 0x3f, sizeof d);
	d[s] = 0; q.push((Node) { s, d[s] });
	while (!q.empty())
	{
		cyc = q.top(); q.pop();
		if (cyc.d != d[cyc.x])continue;
		register int x = cyc.x;
		for (register int i = first[x]; i; i = e[i].from)
			if (d[e[i].v] > d[x] + e[i].w)
			{
				d[e[i].v] = d[x] + e[i].w;
				q.push((Node) { e[i].v, d[e[i].v] });
			}
	}
	return cout << d[t], 0;
}